package com.likou;

import java.util.HashMap;
import java.util.Map;

public class q146 {

    public static void main(String[] args) {
    }


    class LRUCache {

        class LRUNode {
            private LRUNode pre;
            private LRUNode next;
            private Integer key;
            private Integer value;

            public LRUNode() {
            }

            public LRUNode(Integer key, Integer value) {
                this.key = key;
                this.value = value;
                next = null;
                pre = null;
            }
        }

        private Map<Integer, LRUNode> map;
        private int capacity;
        private LRUNode head;
        private LRUNode tail;

        public LRUCache(int capacity) {
            this.map = new HashMap<>(capacity);
            this.capacity = capacity;
            head = new LRUNode(0, 0);
            tail = new LRUNode(0, 0);
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            if (map.containsKey(key)) {
                LRUNode node = map.get(key);
                remove(node);
                insertHead(node);
                return node.value;
            }
            return -1;
        }

        public void put(int key, int value) {
            if (map.containsKey(key)) {
                remove(map.get(key));
            } else if (map.size() >= capacity) {
                LRUNode last = tail.pre;
                remove(last);
                map.remove(last.key);
            }

            LRUNode lruNode = new LRUNode(key, value);
            map.put(key, lruNode);
            insertHead(lruNode);
        }

        private void insertHead(LRUNode node) {
            node.next = head.next;
            node.pre = head;
            head.next.pre = node;
            head.next = node;
        }

        private void remove(LRUNode lruNode) {
            lruNode.pre.next = lruNode.next;
            lruNode.next.pre = lruNode.pre;
        }
    }
}
